package MERGE_22;

import LCommon.ListNode;

public class Solution {
	public ListNode mergeKLists(ListNode[] lists) {
		if (lists.length == 0) {
			return null;
		}
		int k = lists.length;
		while (k > 1) {
			int idx = 0;
			for (int i = 0; i < k; i += 2) {
				if (i == k - 1) {
					lists[idx++] = lists[i];
				} else {
					lists[idx++] = mergeTwoLists_recur(lists[i], lists[i + 1]);
				}
			}
			k = idx;
		}
		return lists[0];

	}

	private ListNode merge2Lists(ListNode l1, ListNode l2) {
		if (l1 == null) {
			return l2;
		}
		if (l2 == null) {
			return l1;
		}
		if (l1.val < l2.val) {
			l1.next = merge2Lists(l1.next, l2);
			return l1;
		}
		l2.next = merge2Lists(l1, l2.next);
		return l2;
	}

	private ListNode mergeTwoLists_recur(ListNode a, ListNode b) {
		if (a == null) {
			return b;
		}
		if (b == null) {
			return a;
		}
		if (a.val < b.val) {
			a.next = mergeTwoLists_recur(a.next, b);
			return a;
		}
		b.next = mergeTwoLists_recur(a, b.next);
		return b;

	}

	private ListNode mergeTwoLists_iter(ListNode a, ListNode b) {
		ListNode head = new ListNode(0);
		ListNode tail = head;
		while (a != null && b != null) {
			if (a.val < b.val) {
				tail.next = a;
				a = a.next;
			} else {
				tail.next = b;
				b = b.next;
			}
			tail = tail.next;
		}
		tail.next = a == null ? b : a;
		return head;
	}
}
